//
// Description: 76. 最小覆盖子串
// Created by Loading on 2022/5/4.
//

#include <bits/stdc++.h>

using namespace std;

string minWindow(string s, string t) {
    // 所有字符数量
    int count = t.size();
    unordered_map<char, int> m_t;
    for (const auto &c : t) {
        ++m_t[c];
    }

    // 最小覆盖子串的长度
    int len = INT_MAX;
    // 滑动窗口起始终止位置
    int start = 0, end = 0;
    // 返回值字符串的起始位置
    int res_start = 0;
    while (end < s.size()) {
        /* 当前字符在 hash 表中数量大于 0 时，找到字符，--count，注意不要忘记 hash 表也要递减 */
        if (m_t[s[end]]-- > 0) {
            --count;
        }
        while (count == 0) { // 全部找到
            if (end - start + 1 < len) {
                len = end - start + 1;
                res_start = start;
            }
            /* 滑动左边界时，当左边界在 hash 表中数量为 0 时，说明左边界所在字符在 t 中出现过且滑出后窗口将不合法，++count，hash 表也要递增 */
            if (m_t[s[start++]]++ == 0) {
                ++count;
            }
        }
        ++end;
    }

    return len == INT_MAX ? "" : s.substr(res_start, len);
}

int main() {
    string s = "a";
    string t = "a";
    auto res = minWindow(s, t);
    cout << res << endl;

    return 0;
}